'''
数学扩展包
'''


'''
等差数列求和
'''
def cal(l,d,cnt,mod = 998244353):
    half = mod / 2 + 1
    r = l + (d % mod) * ((cnt - 1) % mod) % mod
    return (l + r) % mod * cnt % mod * half % mod

def exgcd(a, b):
    if b == 0:
        return a, 1, 0
    r, x, y = exgcd(b, a % b)
    x, y = y, x - (a // b) * y
    return r, x, y

def qmi(x,y,mod):
    ans = 1
    while y:
        if y & 1:
            ans = ans * x % mod
        x = x * x % mod
        y >>= 1
    return ans

def qmi(x,y):
    ans = 1
    while y:
        if y & 1:
            ans = ans * x
        x = x * x
        y >>= 1
    return ans

def gcd(m, n):
    if n == 0:
        m, n = n, m
    while m != 0:
        m, n = n % m, m
    return n

# 返回最低位的0
def lowbit(n):
    return n & (-n)


'''组合数'''
def comb(n, k, mod):
    if n < k:
        return 0
    n %= mod
    p, q = 1, 1
    for i in range(1, k + 1):
        p = p * (n - i + 1) % mod
        q = q * i % mod
    return p * pow(q, mod - 2, mod) % mod


'''
求逆元
'''
def inv(x,mod):
    return pow(x,mod - 2,mod)

'''
容斥原理

我们可以证明，多个集合的并集大小，等于单个集合的和，
减去两个集合交集，加上三个集合交集，减去四个集合交集，以此类推。
'''


